Perfect Squares

Leetcode #279 | Medium | 1-D Динамика

Идея

Динамика... Заводим dp на i+1 элемент, сначала заполняем худшим случаем - dp[i]=i - для i-го числа сойдет сумма из i единиц. Дальше идем от 1 до конца. На каждом шаге начинаем перебирать от j=1 так что j*j <= i. `dp[i] = min(dp[i], 1+dp[i-j*j]). В чем тут логика. Мы нашли новый квадрат, отнимаем его от числа и получили то, что уже посчитали ранее, прибавляем 1 так как использовали еще один, ну и делаем минимум с текущим результатом.

Big-O

• Время O(Nsqrt(N))
• Память O(N)

Код

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
        }
        return dp[n];
    }
}